package top.fengleifeng.question;

import java.util.HashMap;
import java.util.Map;
import top.fengleifeng.util.ListNode;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2021年03月25日 3:38 下午
 */
public class Num82删除排序链表中的重复元素II {

    /**
     * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode() {} ListNode(int
     * val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
     */
    class Solution {

        public ListNode deleteDuplicates(ListNode head) {
            Map<Integer, Integer> map = new HashMap<>();
            ListNode temp = head;
            while (temp != null) {
                map.put(temp.val, map.getOrDefault(temp.val, 0)+1);
                temp = temp.next;
            }

            ListNode top = new ListNode(0);
            ListNode result = top;

            temp = head;
            while (temp != null) {
                int now = map.get(temp.val);
                if (now == 1) {
                    result.next = new ListNode(temp.val);
                    result = result.next;
                }
                temp = temp.next;
            }
            return top.next;
        }
    }

    public static void main(String[] args) {
        ListNode treeNode = new ListNode(1);

        ListNode treeNode2 = new ListNode(2);
        ListNode treeNode3 = new ListNode(3);
        ListNode treeNode4 = new ListNode(3);
        ListNode treeNode5 = new ListNode(4);
        ListNode treeNode6 = new ListNode(4);
        ListNode treeNode7 = new ListNode(5);
        treeNode.next = treeNode2;
        treeNode2.next = treeNode3;
        treeNode3.next = treeNode4;
        treeNode4.next = treeNode5;
        treeNode5.next = treeNode6;
        treeNode6.next = treeNode7;
        ListNode listNode = new Num82删除排序链表中的重复元素II().new Solution().deleteDuplicates(treeNode);
        while (listNode != null) {
            System.out.print(listNode.val + ",");
            listNode = listNode.next;
        }
    }
}
